package com.wk.data.graph;
/**
 * 邻接表无向图
 * 单链表
 */
public class ListNDGraph {
	int size;//顶点数
	Vertex[] vertexLists;//邻接表数组
	
	//顶点类
	class Vertex{
		char ch;
		Vertex next;
		Vertex(char ch){
			this.ch = ch;
		}
		//加到链表尾
		void add(char ch){
            Vertex node=this;
            while(node.next!=null){
                node=node.next;
            }
            node.next=new Vertex(ch);
        }
	}
	
	public ListNDGraph(char[] vertexs,char[][] edges) {
		size = vertexs.length;
		this.vertexLists = new Vertex[size];
		for (int i = 0; i < size; i++) {
			this.vertexLists[i] = new Vertex(vertexs[i]);
		}
		for (char[] c : edges) {
			int p1=getPosition(c[0]);
            vertexLists[p1].add(c[1]);
            // 下面注释掉就是有向表
            int p2=getPosition(c[1]);
            vertexLists[p2].add(c[0]);
		}
	}
	
	 //遍历输出邻接表
    public void print(){
       for(int i=0;i<size;i++){
           Vertex temp=vertexLists[i];
           while(temp!=null){
               System.out.print(temp.ch+" ");
               temp=temp.next;
           }
           System.out.println();
       }
    }
	
	 //跟据顶点名称获取链表下标
    private int getPosition(char ch) {
        for(int i=0; i<size; i++)
            if(vertexLists[i].ch==ch)
                return i;
        return -1;
    }
    
    public static void main(String[] args){
        char[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G','H','I','J','K'};
        char[][] edges = new char[][]{
            {'A', 'C'}, 
            {'A', 'D'}, 
            {'A', 'F'}, 
            {'B', 'C'}, 
            {'C', 'D'}, 
            {'E', 'G'}, 
            {'D', 'G'},
            {'I','J'},
            {'J','G'},};

        ListNDGraph pG;

        long start=System.nanoTime();

        //for(int i=0;i<10000;i++){
            pG = new ListNDGraph(vexs, edges);
            pG.print();   // 打印图 
        //}

        long end=System.nanoTime();

        System.out.println(end-start);

    }
}
